class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        vector<pair<int, int>> jobs;
        int n = profit.size(), res = 0, i = 0, best = 0;
        for (int j = 0; j < n; ++j) {
            jobs.emplace_back(difficulty[j], profit[j]);
        }
        sort(jobs.begin(), jobs.end());
        sort(worker.begin(), worker.end());
        for (auto& e : worker)
        {
            while (i < n && jobs[i].first <= e)
            {
                best = max(best, jobs[i].second);
                i++;
            }
            res += best;
        }
        return res;
    }



};
class SnapshotArray {
public:
    size_t cut_snap_id = 0;
    vector<vector<pair<int, int>>> nums;
    SnapshotArray(int length)
        :nums(length)
    {

    }

    void set(int index, int val) {
        nums[index].emplace_back(cut_snap_id, val);
    }

    int snap() {
        return cut_snap_id++;
    }

    int get(int index, int snap_id) {
        auto& h = nums[index];
        int l = 0, r = nums[index].size();

        while (l < r)
        {
            size_t mid = (l + r) / 2;
            if (h[mid].first < snap_id)
                l = mid + 1;
            else
                r = mid;

        }
        return l == 0 ? 0 : h[l].second;
        // auto x = upper_bound(nums[index].begin(), nums[index].end(), pair{snap_id + 1, -1});
        // return x == nums[index].begin() ? 0 : prev(x)->second;

    }
};